 //86.分隔链表
 //https://leetcode.cn/problems/partition-list/description
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* cur = head;
        //组织<x的节点
        ListNode* head1 = new ListNode(-1);
        ListNode* cur1 = head1;
        //组织>=x的节点
        ListNode* head2 = new ListNode(-2);
        ListNode* cur2 = head2;
        //利用归并排序思想 归并排序是稳定的排序 所以归并不会打乱顺序
        while(cur)
        {
            if(cur->val < x)
            {
                cur1->next = cur;
                cur1 = cur1->next;
            }
            else
            {
                cur2->next = cur;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        cur2->next = nullptr;
        cur1->next = head2->next;
        cur = head1->next;
        delete head1;
        delete head2;
        return cur;
    }
};